package com.study.leetcode;

public class Solution_80 {
    //标记法
    public static int removeDuplicates(int[] nums) {
        int len = nums.length;
        int min = Integer.MIN_VALUE;
        int newLen = len;
        if (len == 0) {
            return 0;
        }
        int count = 1;
        int pre = nums[0];
        for (int i = 1; i < len; i++) {
            if (pre == nums[i]) {
                count++;
                if (count > 2) {
                    nums[i] = min;
                    newLen--;
                }
            } else {
                pre = nums[i];
                count = 1;
            }

        }

        for (int i = 0; i < newLen; i++) {
            if (nums[i] == min) {
                pre = i;
                while (pre < len && nums[pre] == min) {
                    pre++;
                }
                nums[i] = nums[pre];
                nums[pre] = min;
            }
        }
        return newLen;
    }

    //直接插入法
    public static int removeDuplicates1(int[] nums) {
        int newLen = 0;
        for (int i = 0; i < nums.length; i++) {
            if (newLen < 2 || nums[i] > nums[newLen - 2]) {
                nums[newLen++] = nums[i];
            }
        }
        return newLen;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 2, 2, 2, 2, 3};
        int i = removeDuplicates1(nums);
        for (int j = 0; j < i; j++) {
            System.out.print(nums[j] + ",");
        }
    }
}
